package com.youth.day01;

/**
 *  归并排序
 * @author Jinx
 * @date 2021/6/14 0:10
 */
public class MergeSort {


    /**
     *  时间复杂度：O(nlog2ⁿ)
     *  分析：
     *  递归：log2ⁿ    当数组长度为n时，每次对半递归。
     *  合并：n
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }

        int[] left = new int[arr.length/2];
        int[] right = new int[arr.length - left.length];
        System.arraycopy(arr, 0, left, 0, left.length);
        System.arraycopy(arr, left.length, right, 0, right.length);
        left = sort(left);
        right = sort(right);

        // 两个有序数组合并
        int i = 0, j = 0;
        for (int k = 0; k < arr.length; k++) {
            if(i == left.length){
                System.arraycopy(right, j, arr, i+j, right.length - j);
                break;
            }
            if(j == right.length){
                System.arraycopy(left, i, arr, i+j, left.length - i);
                break;
            }
            arr[k] = left[i] < right[j] ? left[i++] : right[j++];
        }

        return arr;
    }
}
